package leetcode_core.leetcode_1;

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {
    List<String> ans = new ArrayList<String>();
    public List<String> generateParenthesis(int n) {
        if(n==0){
            return ans;
        }
        StringBuilder track = new StringBuilder();
        backtrack(track,n,n);
        return null;
    }

    //路径,选择列表,i是当前的位置,n是规定的括号列表长度
    private void backtrack(StringBuilder track,int left,int right){//可用的左括号数量为left个,可用的右括号数量为right个
        if(left<0 || right<0){
            return;
        }
        //如果左括号用得少,那么肯定不合法
        if(left>right){
            return;
        }
        //当所有括号都刚好用完的时候,那么就得到一个合法的组合了
        if(left ==0 && right ==0){
            ans.add(track.toString());
            return;
        }
        char[] choices= new char[]{'(',')'};
        for(int j = 0;j<choices.length;j++){
            //做选择
            track.append(choices[j]);
            //穷举下一个位置
            if(j== 0){
                backtrack(track,left-1,right);
            }
            if(j==1){
                backtrack(track,left,right-1);
            }
            //撤销选择
            track.deleteCharAt(track.length()-1);
        }
    }
}
